/*
题目: 删除无效的括号
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。
https://leetcode.cn/problems/remove-invalid-parentheses/
 */
public class RemoveInvalidParentheses {
    List<String> result = new ArrayList<> ();
    int n = 0;

    public List<String> removeInvalidParenthesesBetter(String s) {
        Set<String> items = new HashSet<>();
        n = s.length();
        items.add(s);

        while (result.isEmpty()) {
            for (String str : items) {
                if (isValid(str, str.length())) {
                    result.add(str);
                }
            }
            if (! result.isEmpty())    return result;

            Set<String> nextSet = new HashSet<> (); //每次记录下一层深度
            for (String str : items) {
                for (int i = 0; i < str.length(); i ++) {
                    if (str.charAt(i) == '(' || str.charAt(i) == ')') {
                        nextSet.add(str.substring(0, i) + str.substring(i + 1, str.length()));
                    }
                }
            }
            items = nextSet; //更新 items 哈希表值
        }

        return result;
    }

    // 原始版本
    List<String> src = new ArrayList<> ();

    public List<String> removeInvalidParentheses(String s) {
        if (isValid(s, s.length())) {
            src.add(s);
            return src;
        }
        Set<String> visited = new HashSet<> ();
        visited.add(s);

        Queue<String> queue = new LinkedList<> ();
        queue.offer(s);

        while (!queue.isEmpty()) {
            if (!src.isEmpty())
                return src;

            int size = queue.size();

            while (size-- > 0) {
                String cur = queue.poll();
                int len = cur.length();

                for (int i = 0; i < len; i++) {
                    String str = cur.substring(0, i) + cur.substring(i + 1, len);
                    if (!visited.contains(str)) {
                        if (isValid(str, str.length())) {
                            src.add(str);
                        }
                        visited.add(str);
                        queue.offer(str);
                    }
                }
            }

        }
        return src;
    }

    private boolean isValid(String s, int end) {
        int count = 0;
        for (int i = 0; i < end; i ++) {
            char ch = s.charAt(i);
            if (count < 0)
                return false;

            if (Character.isLetter(ch))
                continue ;

            if (ch == '(') {
                count ++;
            } else {
                count --;
            }
        }

        return count == 0;
    }
}
